package cn.edu.njust.alg.leetcode;

import java.util.HashMap;
import java.util.HashSet;

public class Solution {

	public static void main(String[] args) {
		test_3();
	}

	// 104 Maximum Depth of Binary Tree
	public static int maxDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
	}

	public static void test_104() {

	}

	// 203
	public ListNode removeElements(ListNode head, int val) {

		while (head != null && head.val == val) {
			head = head.next;
		}
		if (head == null) {
			return head;
		}
		ListNode pre = head;
		ListNode p = head.next;

		while (p != null) {
			if (p.val == val) {
				pre.next = p.next;
				p = pre.next;
			} else {
				pre = p;
				p = p.next;
			}
		}

		return head;
	}

	public static void test_203() {
		ListNode node1 = new ListNode(5);
		ListNode node2 = new ListNode(6);
		ListNode node3 = new ListNode(6);
		ListNode node4 = new ListNode(6);
		ListNode node5 = new ListNode(6);
		ListNode node6 = new ListNode(6);
		ListNode node7 = new ListNode(1);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node7;
		node7.next = null;
		ListNode retListNode = new Solution().removeElements(node1, 6);
		printListNode(retListNode);

	}

	/*
	 * 第206题
	 * 
	 * Reverse a singly linked list.
	 */
	public ListNode reverseList(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode tmp = null;
		ListNode pre = head;
		ListNode p = head.next;
		pre.next = null;
		while (p != null) {
			tmp = p.next;
			p.next = pre;
			pre = p;
			p = tmp;
		}

		return pre;
	}

	// 第125题
	/*
	 * Given a string, determine if it is a palindrome, considering only
	 * alphanumeric characters and ignoring cases.
	 * 
	 * For example, "A man, a plan, a canal: Panama" is a palindrome.
	 * "race a car" is not a palindrome.
	 * 
	 * Note: Have you consider that the string might be empty? This is a good
	 * question to ask during an interview.
	 * 
	 * For the purpose of this problem, we define empty string as valid
	 * palindrome.
	 */

	public boolean isPalindrome(String s) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < s.length(); i++) {
			Character c = s.charAt(i);
			if (Character.isLetterOrDigit(c)) {
				sb.append(Character.toLowerCase(c));
			}
		}
		if (sb.length() == 0) {
			return true;
		}
		int len = sb.length();
		for (int i = 0; i <= len / 2; i++) {
			if (sb.charAt(i) != sb.charAt(len - 1 - i)) {
				return false;
			}
		}
		return true;
	}

	public static void test_125() {
		//String i = "A man, a plan, a canal: Panama";
		String j = "1a2";
		System.out.println(new Solution().isPalindrome(j));
	}

	// num 124
	/*
	 * Given a binary tree and a sum, determine if the tree has a root-to-leaf
	 * path such that adding up all the values along the path equals the given
	 * sum.
	 * 
	 * For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11
	 * 13 4 / \ \ 7 2 1
	 * 
	 * return true, as there exist a root-to-leaf path 5->4->11->2 which sum is
	 * 22.
	 */
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		return throuht(root, sum);
	}

	public static boolean throuht(TreeNode t, int sum) {
		if (t == null) {
			return false;
		}
		int sumadd = sum - t.val;
		if (t.left == null && t.right == null) {
			if (sumadd == 0) {
				return true;
			} else {
				return false;
			}
		}
		return throuht(t.left, sumadd) || throuht(t.right, sumadd);
	}

	public static void test_124() {
		TreeNode root = new TreeNode(5);
		TreeNode t1 = new TreeNode(4);
		TreeNode t2 = new TreeNode(8);
		TreeNode t3 = new TreeNode(11);
		TreeNode t4 = new TreeNode(13);
		TreeNode t5 = new TreeNode(4);
		TreeNode t6 = new TreeNode(7);
		TreeNode t7 = new TreeNode(2);
		TreeNode t8 = new TreeNode(1);

		root.left = t1;
		root.right = t2;

		t1.left = t3;
		t1.right = null;
		t2.left = t4;
		t2.right = t5;
		t3.left = t6;
		t3.right = t7;
		t4.left = null;
		t4.right = null;
		t5.left = null;
		t5.right = t8;
		t6.left = null;
		t6.right = null;
		t7.left = null;
		t7.right = null;
		t8.left = null;
		t8.right = null;

		System.out.println(throuht(root, 22));
	}

	// 62
	public static int uniquePaths(int m, int n) {
		// if (m == 1 || n == 1) {
		// return 1;
		// } else {
		// return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
		// }
		int[][] res = new int[m][n];
		int i, j;
		for (i = 0; i < m; i++) {
			res[i][0] = 1;
		}
		for (i = 0; i < n; i++) {
			res[0][i] = 1;
		}
		for (i = 1; i < m; i++) {
			for (j = 1; j < n; j++) {
				res[i][j] = res[i - 1][j] + res[i][j - 1];
			}
		}

		return res[m - 1][n - 1];
	}

	public static void test_62() {
		System.out.println(uniquePaths(7, 8));
	}

	// 58
	public int lengthOfLastWord(String s) {
		String[] strs = s.split(" ");
		if (strs.length < 1) {
			return 0;
		} else {
			return strs[strs.length - 1].length();
		}
	}

	public static void test_58() {
		String[] strs = { "hello world", "hello" };
		Solution solution = new Solution();
		for (String str : strs) {
			System.out.println(solution.lengthOfLastWord(str));
		}
	}

	// 第七题
	public int reverse(int x) {
		int t = x;
		long sum = 0;
		while (t != 0) {
			int s = t % 10;
			sum = 10 * sum + s;
			t = t / 10;
		}

		if (sum > Integer.MAX_VALUE) {
			sum = 0;
		} else if (sum < Integer.MIN_VALUE) {
			sum = 0;
		}
		return (int) sum;
	}

	public static void test_7() {
		int i = 147483648;
		System.out.println(new Solution().reverse(i));
		System.out.println(Integer.reverse(i));
	}

	/*
	 * 第六题
	 * 
	 * The string "PAYPALISHIRING" is written in a zigzag pattern on a given
	 * number of rows like this: (you may want to display this pattern in a
	 * fixed font for better legibility)
	 * 
	 * P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR"
	 * Write the code that will take a string and make this conversion given a
	 * number of rows:
	 * 
	 * string convert(string text, int nRows); convert("PAYPALISHIRING", 3)
	 * should return "PAHNAPLSIIGYIR".
	 */
	public String convert(String s, int numRows) {
		if (numRows == 1) {
			return s;
		}
		int period = 2 * numRows - 2;
		StringBuffer bf = new StringBuffer();
		for (int i = 0; i < numRows; i++) {
			if (i == 0 || i == numRows - 1) {
				int j = i;
				while (j < s.length()) {
					bf.append(s.charAt(j));
					j += period;
				}
			} else {
				int j = i;
				while (j < s.length()) {
					bf.append(s.charAt(j));
					if (j + period - 2 * i < s.length()) {
						bf.append(s.charAt(j + period - 2 * i));
					}
					j += period;
				}
			}

		}
		return bf.toString();
	}

	public static void test_6() {
		//String s = "PAYPALISHIRING";
		System.out.println(new Solution().convert("A", 1));
	}

	/**
	 * 第三题
	 * 
	 * Given a string, find the length of the longest substring without
	 * repeating characters. For example, the longest substring without
	 * repeating letters for "abcabcbb" is "abc", which the length is 3. For
	 * "bbbbb" the longest substring is "b", with the length of 1.
	 */
	public static int lengthOfLongestSubstring(String s) {
		if (s == null) {
			return 0;
		}
		if (s.length() <= 1) {
			return s.length();
		}
		HashSet<Character> set = new HashSet<Character>();
		int max = 0;
		int j = 0, i = 0;
		char tc;
		for (i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (set.contains(c)) {
				if (max < i - j) {
					max = i - j;
				}
				while ((tc = s.charAt(j++)) != c) {
					set.remove(tc);
				}

			} else {
				set.add(c);
			}
		}
		return Math.max(max, i - j);
	}

	public static void test_3() {
		String s = "bbbabbabc";
		System.out.println(Solution.lengthOfLongestSubstring(s));
	}

	/**
	 * 第二题
	 * 
	 * You are given two linked lists representing two non-negative numbers. The
	 * digits are stored in reverse order and each of their nodes contain a
	 * single digit. Add the two numbers and return it as a linked list.
	 * 
	 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
	 */

	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		int c = 0;
		ListNode head, pre, p;
		ListNode p1 = l1;
		ListNode p2 = l2;
		head = new ListNode(0);
		head.next = null;
		pre = head;

		while (p1 != null && p2 != null) {
			int sum = p1.val + p2.val + c;
			int d = sum % 10;
			c = sum / 10;
			p = new ListNode(d);
			p.next = null;
			pre.next = p;
			pre = p;
			p1 = p1.next;
			p2 = p2.next;
		}
		while (p1 != null) {
			int sum = p1.val + c;
			int d = sum % 10;
			c = sum / 10;
			p = new ListNode(d);
			p.next = null;
			pre.next = p;
			pre = p;
			p1 = p1.next;
		}
		while (p2 != null) {
			int sum = p2.val + c;
			int d = sum % 10;
			c = sum / 10;
			p = new ListNode(d);
			p.next = null;
			pre.next = p;
			pre = p;
			p2 = p2.next;
		}
		if (c != 0) {
			p = new ListNode(c);
			p.next = null;
			pre.next = p;
			pre = p;
		}

		return head.next;
	}

	public static void test_2() {
		ListNode node1 = new ListNode(2);
		ListNode node2 = new ListNode(4);
		ListNode node3 = new ListNode(3);
		node1.next = node2;
		node2.next = node3;
		node3.next = null;

		ListNode node4 = new ListNode(5);
		ListNode node5 = new ListNode(6);
		ListNode node6 = new ListNode(4);
		node4.next = node5;
		node5.next = node6;
		node6.next = null;
		ListNode res = new Solution().addTwoNumbers(node1, node4);
		printListNode(res);
	}

	public static void printListNode(ListNode L) {
		System.out.print("(");
		ListNode node = L;
		while (node != null) {
			System.out.printf("%d ", node.val);
			node = node.next;
		}
		System.out.print(")");
		System.out.println();
	}

	// 第一题
	public int[] twoSum(int[] nums, int target) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			Integer n = map.get(nums[i]);
			if (n == null) {
				map.put(nums[i], i);
			}
			int another = target - nums[i];
			Integer ano = map.get(another);
			if (ano != null && ano < i) {
				return new int[] { ano + 1, i + 1 };
			}
		}
		return null;
	}

	//
	public int[] twoSum_1(int[] nums, int target) {
		for (int i = 0; i < nums.length; i++) {
			int another = target - nums[i];
			for (int j = i + 1; j < nums.length; j++) {
				if (another == nums[j]) {
					return new int[] { i + 1, j + 1 };
				}
			}
		}
		return null;
	}

}


